Word Ladder II

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list

For example,

Given:

beginWord = "hit"

endWord = "cog"

wordList = ["hot","dot","dog","lot","log"]

Return

  1.   [
  2.     ["hit","hot","dot","dog","cog"],
  3.     ["hit","hot","lot","log","cog"]
  4.   ]

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Solution:

  1. public class Solution {
  2.   public List<List<String>> findLadders(String start, String end, Set<String> dict) {
  3.     // hash set for both ends
  4.     Set<String> set1 = new HashSet<String>();
  5.     Set<String> set2 = new HashSet<String>();
  7.     // initial words in both ends
  8.     set1.add(start);
  9.     set2.add(end);
  11.     // we use a map to help construct the final result
  12.     Map<String, List<String>> map = new HashMap<String, List<String>>();
  14.     // build the map
  15.     helper(dict, set1, set2, map, false);
  17.     List<List<String>> res = new ArrayList<List<String>>();
  18.     List<String> sol = new ArrayList<String>(Arrays.asList(start));
  20.     // recursively build the final result
  21.     generateList(start, end, map, sol, res);
  23.     return res;
  24.   }
  26.   boolean helper(Set<String> dict, Set<String> set1, Set<String> set2, Map<String, List<String>> map, boolean flip) {
  27.     if (set1.isEmpty()) {
  28.       return false;
  29.     }
  31.     if (set1.size() > set2.size()) {
  32.       return helper(dict, set2, set1, map, !flip);
  33.     }
  35.     // remove words on current both ends from the dict
  36.     dict.removeAll(set1);
  37.     dict.removeAll(set2);
  39.     // as we only need the shortest paths
  40.     // we use a boolean value help early termination
  41.     boolean done = false;
  43.     // set for the next level
  44.     Set<String> set = new HashSet<String>();
  46.     // for each string in end 1
  47.     for (String str : set1) {
  48.       for (int i = 0; i < str.length(); i++) {
  49.         char[] chars = str.toCharArray();
  51.         // change one character for every position
  52.         for (char ch = 'a'; ch <= 'z'; ch++) {
  53.           chars[i] = ch;
  55.           String word = new String(chars);
  57.           // make sure we construct the tree in the correct direction
  58.           String key = flip ? word : str;
  59.           String val = flip ? str : word;
  61.           List<String> list = map.containsKey(key) ? map.get(key) : new ArrayList<String>();
  63.           if (set2.contains(word)) {
  64.             done = true;
  66.             list.add(val);
  67.             map.put(key, list);
  68.           } 
  70.           if (dict.contains(word)) {
  71.             set.add(word);
  73.             list.add(val);
  74.             map.put(key, list);
  75.           }
  76.         }
  77.       }
  78.     }
  80.     // early terminate if done is true
  81.     return done || helper(dict, set2, set, map, !flip);
  82.   }
  84.   void generateList(String start, String end, Map<String, List<String>> map, List<String> sol, List<List<String>> res) {
  85.     if (start.equals(end)) {
  86.       res.add(new ArrayList<String>(sol));
  87.       return;
  88.     }
  90.     // need this check in case the diff between start and end happens to be one
  91.     // e.g "a", "c", {"a", "b", "c"}
  92.     if (!map.containsKey(start)) {
  93.       return;
  94.     }
  96.     for (String word : map.get(start)) {
  97.       sol.add(word);
  98.       generateList(word, end, map, sol, res);
  99.       sol.remove(sol.size() - 1);
  100.     }
  101.   }
  102. }